\section{Related Work}
\label{sec:rel}
Various interesting approaches for {\em team formation} have been studied over the years. In operations research~\cite{CL, ZK, BDD, WOMJ}, the problem is defined as finding an optimal match between people and demanded functional requirements. It is often solved using techniques such as simulated annealing, branch-and-cut or genetic algorithms~\cite{BDD, ZK, WOMJ}. Another interesting problem formulation requires taking into consideration the psychological aspects of the individuals involved in order to form a team of efficient collaboration, e.g, the work by Fitzpatrick and Askin ~\cite{FA}, and Chen and Lin in~\cite{CL}. However, all these approaches do not use the possible presence of a social graph structure between the individuals. Therefore, these approaches are complementary to ours. Further, Gaston et al.~\cite{GSJ} provide an experimental study on the effects of a graph structure among individuals on the performance of a team. 

Our problem formulation differs from these fundamentally by requiring a solution where the optimality is determined based on the properties associated with a social graph structure among the individuals. In particular, we aim to form a team that contains at least $k_i$ nodes of skill $i$ such that the density of the resulting solution subgraph is maximized. A similar problem has been addressed by Lappas et. al.~\cite{LLT}. They try to find a team that contains at least $1$ node for each skill $i$, with the cost of a solution measured in terms of either a diameter or a minimum spanning tree. Our problem definition generalizes this requirement and suggests a new density based measure for solution's objective.
% subgraph as opposed to minimum diameter subgraph or minimum spanning tree. 

The problem of finding size-bound densest subgraphs is well-studied. Finding a maximum density subgraph on an undirected graph can be solved in polynomial time~\cite{G84, L}. However, the problem becomes NP-hard when a size restriction is enforced. In particular, finding a maximum density subgraph of size exactly $k$ is NP-hard~\cite{AHI, FKP} and no approximation scheme exists under a reasonable complexity assumption~\cite{K}.
% Recently, Andersen and Chellapilla~\cite{AC} considered approximation algorithms to this and other similar problems. 
Khuller and Saha~\cite{KS} considered the problem of finding densest subgraphs with size restrictions and showed that these are NP-hard. Khuller and Saha ~\cite{KS} and also Andersen and Chellapilla ~\cite{AC} gave constant factor approximation algorithms. Our problem definition varies from these because we not only require to find the maximum density subgraph of size at least $k$, but, we also require that this subgraph contains at least $k_i$ nodes of property $i$ such that $k = \sum_{i}{k_i}$. Thus, we also generalize past work on finding size-bound maximum density subgraphs.
